package string;

class SuffixArray {

	public int sa[][], rank[][], h[], height[], cnt[], bit, n;

	public static final char ch = 'a' - 1;

	public void build(String s) {
		n = s.length();
		bit = 0;
		sa = new int[2][n];
		rank = new int[2][n];
		h = new int[n];
		height = new int[n];
		cnt = new int[27];
		int k = 1;
		for (int i = 0; i < n; i++)
			cnt[s.charAt(i) - ch]++;
		for (int i = 1; i < 27; i++)
			cnt[i] += cnt[i - 1];
		for (int i = 0; i < n; i++)
			sa[bit][--cnt[s.charAt(i) - ch]] = i;
		rank[bit][sa[bit][0]] = 0;
		for (int i = 1; i < n; i++) {
			rank[bit][sa[bit][i]] = rank[bit][sa[bit][i - 1]];
			if (s.charAt(sa[bit][i]) != s.charAt(sa[bit][i - 1]))
				rank[bit][sa[bit][i]]++;
		}
		cnt = new int[n];
		for (k = 1; k < n && rank[bit][sa[bit][n - 1]] < n - 1; k <<= 1) {
			for (int i = 0; i < n; i++)
				cnt[rank[bit][sa[bit][i]]] = i + 1;

			for (int i = n - 1; i >= 0; i--)
				if (sa[bit][i] >= k)
					sa[1 - bit][--cnt[rank[bit][sa[bit][i] - k]]] = sa[bit][i]
							- k;

			for (int i = n - k; i < n; i++)
				sa[1 - bit][--cnt[rank[bit][i]]] = i;

			rank[1 - bit][sa[1 - bit][0]] = 0;

			for (int i = 1; i < n; i++) {
				rank[1 - bit][sa[1 - bit][i]] = rank[1 - bit][sa[1 - bit][i - 1]];
				if (rank[bit][sa[1 - bit][i]] != rank[bit][sa[1 - bit][i - 1]]
						|| sa[1 - bit][i] + k >= n
						|| sa[1 - bit][i - 1] + k >= n
						|| rank[bit][sa[1 - bit][i] + k] != rank[bit][sa[1 - bit][i - 1]
								+ k])
					rank[1 - bit][sa[1 - bit][i]]++;
			}
			bit = 1 - bit;
		}

		int p, q;
		for (int i = 0; i < n; i++) {
			if (rank[bit][i] == 0)
				h[i] = 0;
			else {
				if (i == 0 || h[i - 1] < 2) {
					p = i;
					q = sa[bit][rank[bit][i] - 1];
				} else {
					p = i + h[i - 1] - 1;
					q = sa[bit][rank[bit][i] - 1] + h[i - 1] - 1;
				}
				while (p < n && q < n && s.charAt(p) == s.charAt(q)) {
					p++;
					q++;
				}
				h[i] = p - i;
			}
		}
		for (int i = 0; i < n; i++)
			height[i] = h[sa[bit][i]];
	}

}
